/**
 * Definition for binary tree with next pointer.
 * function TreeLinkNode(val) {
 *     this.val = val;
 *     this.left = this.right = this.next = null;
 * }
 */

/**
 * @param {TreeLinkNode} root
 * @return {void} Do not return anything, modify tree in-place instead.
 */
var connect = function(root) {
    if(!root)return ;

    let pre = root,
        head = root.left || root.right,
        cur = head;

    if(!head)return;

    while(cur){
        if(pre.left){
            cur.next = pre.left;
            cur = cur.next;
        }
        if(pre.right){
            cur.next = pre.right;
            cur = cur.next;
        }
        pre = pre.next;
        if(!pre){
            cur.next = null;
            cur = head.left || head.right;
            while(!cur){
                head = head.next;
                if(!head)break;
                cur = head.left || head.right;
            }
            pre = head;
            head = cur;
        }
    }

};